/**
 * https://leetcode.cn/problems/rotated-digits/submissions/572302742/
 * 788. 旋转数字
 * medium 陈贝纯 2024.10.13
 * 数位dp
 */


class Solution {
public:
    int sum=0;
    int l=0;
    int j;
    int t;
    int visit=0;
    vector<int> dp={0,1,2,5,6,8,9};
    void dfs(int num,int n){
        if(n>=l){
            if(t==1||t==8){
                if(visit>0&&num<=j)
                sum++;
            }else if(num<=j)
                sum++;
            return;
        }
        for(int i=0;i<7;++i){
            if(dp[i]==2||dp[i]==5||dp[i]==6||dp[i]==9){
                visit++;
                dfs(num*10+dp[i],n+1);
                visit--;
            }
            else
                dfs(num*10+dp[i],n+1);
        }
    }
    int rotatedDigits(int n) {
        j=n;
        t=n;
        while(t/10){
            l++;
            t/=10;
        }
        int current=0;
        int j=1;
        for(int i=0;i<l;++i){
            sum+=(4*j+2*sum);
            j*=7;
        }
        int h=0;
        if(t>1){
            current=1;
            if(t>8)
            current=2;
        }
        if(t>2){
            h=1;
            if(t>5){
                h=2;
                if(t>6){
                    h=3;
                }
            }
        }
        sum+=(h*j+current*sum);
        if(t!=3&&t!=4&&t!=7)
        dfs(t,0);
        return sum;
    }
};